Randomness and Computation Joint Workshop “New

As for many complex systems, network structures are important as their backbone. From research on dynamics of epidemic and disease spreading, it has been revealed that network structures have large influence on spreading phenomena, such as computer virus infections, epidemiology, and rumor dynamics [1]. The network structures affect various dynamics on the networks, and conversely various dynamics might affect the network structures and could change them. Therefore research on network structures is important, and then research on complex networks has attracted the attention of a lot of scientists [2,3]. Recently, investigations on a wide variety of networks, such as World Wide Web [4], the Internet backbone [5], social networks [6], the metabolic networks [7], and so on have clarified that complex networks in nature are more complex than ordinary random networks proposed by Erdős and Renýi [2, 8]. One of the remarkable properties of the real complex networks is a scale-free property. If we define the degree distribution P (k) as the probability that a node is connected to k other nodes, networks with the scale-free property are characterized by a power-law behavior, P (k) ∼ k−γ, where γ is a characteristic degree exponent. Barabási and Albert [9] have proposed a model (so-called BA model) with the concepts of growth and preferential attachment in order to explain emergence of the scale-free networks in nature. The concep